#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
    int dirs[4][2] = { {0, 1},
                      {1, 0},
                      {0, -1},
                      {-1, 0} };
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n));
        int num = n * n, count = 1;
        int r = 0, c = 0, d = 0;
        unordered_map<int, int> hash;
        while (num--)
        {
            ans[r][c] = count++;
            hash[r * n + c]++;
            r += dirs[d][0];
            c += dirs[d][1];
            if (r < 0 || r >= n || c < 0 || c >= n || hash[r * n + c])
            {
                r -= dirs[d][0];
                c -= dirs[d][1];
                d = (d + 1) % 4;
                r += dirs[d][0];
                c += dirs[d][1];
            }
        }
        return ans;
    }
};
int main()
{
    int n = 3;
    Solution().generateMatrix(n);
    return 0;
}